#include<bits/stdc++.h>
#define int long long
#define inf 2000
using namespace std;
int T,n,a[100005],b[2005],lft[2005],lstp[2005],fp[2005],dp[2005][2005],ans;
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(n>2000)continue;
        for(int i=2;i<=n;i++)b[i]=b[i-1]+(a[i]==a[i-1])*a[i];
        for(int i=1;i<=inf;i++)lstp[i]=0;
        for(int i=1;i<=n;i++){lft[i]=lstp[a[i]];lstp[a[i]]=i;}
        for(int i=n;i>=1;i--)fp[a[i]]=i;
        for(int i=1;i<=n;i++){
            for(int l=1;l<=inf;l++)dp[i][l]=dp[i-1][l];
            for(int l=1;l<=inf;l++)dp[i][a[i-1]]=max(dp[i][a[i-1]],dp[i-1][l]);
            if(!lft[i])continue;
            if(a[i]==a[i-1])for(int l=1;l<=inf;l++)dp[i][l]=max(dp[i][l],dp[i-1][l]+a[i]);
            else for(int l=1;l<=inf;l++)if(fp[l]<=lft[i])dp[i][a[i-1]]=max(dp[i][a[i-1]],dp[lft[i]][l]+a[i]+(b[i-1]-b[lft[i]+1])+(a[lft[i]+1]==l)*l);
        }ans=0;
        for(int i=1;i<=inf;i++)ans=max(ans,dp[n][i]);cout<<ans<<"\n";
    }
}
